#include<iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <set>
#include <map>
using namespace std;
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>>ans = dfs(nums, nums.size());
        return ans;
    }
    vector<vector<int>> dfs(vector<int>& nums, int n)
    {
        vector<vector<int>>ans, at;
        if (n == 1)
        {
            vector<int>t;
            t.push_back(nums[0]);
            ans.push_back(t);
            return ans;
        }
        sort(nums.begin(), nums.begin() + n);
        for (int i = n - 1; i >= 0; i--)
        {
            if (i != n - 1 && nums[i] == nums[i + 1])continue;
            int t = nums[i];
            nums[i] = nums[n - 1];
            nums[n - 1] = t;
            at = dfs(nums, n - 1);
            for (int j = 0; j < at.size(); j++)
            {
                at[j].push_back(t);
                ans.push_back(at[j]);
            }
            nums[n - 1] = nums[i];
            nums[i] = t;
        }
        sort(nums.begin(), nums.begin() + n);
        return ans;
    }
};
int main()
{
    Solution s;

}
